23 Long-Term Behavior of MC

1 Periodic & Aperiodic

We've introduced common concepts about Markov chain.
Consider a $2 -$ state MC. The transition matrix is $P = [\begin{matrix} 1 - a & a \\ b & 1 - b \end{matrix}]$ , where $a, b \in (0, 1]$ . Then $P^{n} = \frac{1}{a + b} [\begin{matrix} b & a \\ b & a \end{matrix}] + \frac{(1 - a - b)^{n}}{a + b} [\begin{matrix} a & - a \\ - b & b \end{matrix}] .$

Suppose $(a, b) = (1, 1)$ . Then $P^{n} = \frac{1}{2} [\begin{matrix} 1 & 1 \\ 1 & 1 \end{matrix}] + \frac{(- 1)^{n}}{2} [\begin{matrix} 1 & - 1 \\ - 1 & 1 \end{matrix}] = {\begin{aligned} [\begin{array}{c} 0 & 1 \\ 1 & 0 \end{array}], n is odd, \\ [\begin{array}{c} 1 & 0 \\ 0 & 1 \end{array}], n is even . \end{aligned}$
Suppose $(a, b) \neq (1, 1)$ , $| 1 - a - b | < 1$ , so $lim_{n \to \infty} (1 - a - b)^{n} = 0$ , so $lim_{n \to \infty} P^{n} = \frac{1}{a + b} [\begin{matrix} b & a \\ b & a \end{matrix}] .$
In fact, $π = \frac{1}{a + b} [\begin{matrix} b & a \end{matrix}]$ is the unique stationary distribution of the Markov Chain. ( $π P = π$ )
In general, every finite-state Markov Chain has a stationary distribution $π$ and by irreducibility, $π$ is unique.

Question: under what condition is $lim_{n \to \infty} [P^{n}]_{i j} = lim_{n \to \infty} P (X_{n} = j | X_{0} = i) = π_{j}, \forall i, j \in S$ ?

Period

The period $d (i)$ of a state $i \in S$ is defined as $d (i) = \gcd {n \in N | [P^{n}]_{i i} > 0} .$

For example above, $d (1) = d (2) = 2$ .

Periodic / Aperiodic

A state $i \in S$ is periodic / aperiodic, if $d (i) > 1 / d (i) = 1$ .

Claim

If $i \leftrightarrow j$ , then $d (i) = d (j)$ .

Suppose a class $C$ of period $d$ . Then there exists a partition $C = B_{0} \cup \dots \cup B_{d - 1}$ .

Theorem

Let $C$ be a class in a finite-state Markov Chain with period $d$ . Then $C$ can be partitioned into $d$ subsets $C = B_{0} \cup \dots \cup B_{d - 1}$ s.t. all transitions from $B_{K \mod d}$ go to $B_{K + 1 \mod d}$ .

Theorem

If a MC with finite state space $S$ is irreducible and aperiodic, then

(Regular or ergodic): $\exists k \in N^{*}$ , s.t. $[P^{k}]_{i j} > 0, \forall i, j \in S$ .
(Limiting distribution): $lim_{n \to \infty} [P^{n}]_{i j} = π_{j}, \forall i, j \in S$ where $π = (π_{i})_{i \in S}$ is the unique stationary distribution. (or in matrix notation $lim_{n \to \infty} P^{n} = 1 π = [\begin{matrix} π \\ ⋮ \\ π \end{matrix}] .$

2 Convergence Theorem

Another interpretation of the stationary distribution for an irreducible finite MC:

Lemma

Consider an irreducible finite MC with transition matrix $P$ and the unique stationary distribution $π$ . Then $lim_{n \to \infty} \frac{I + P + \dots + P^{n}}{n + 1} = [\begin{matrix} π \\ ⋮ \\ π \end{matrix}] .$

$H_{j}^{(n)} = \frac{1}{n + 1} \sum_{k = 0}^{n} 1 {X_{k} = j}$ is the fraction of time spent in state $j$ during steps $0, 1, \dots, n$ .

\begin{aligned} E [H_{j}^{(n)} | X = i] & = \frac{1}{n + 1} \sum_{k = 0}^{n} \underset{[P^{k}]_{i j}}{\underset{⏟}{P (X_{k} = j | X_{0} = i)}} . \end{aligned}

By the lemma, this $\to π_{j}$ as $n \to \infty$ .

WLLN for Irreducible Finite MC

$\forall ε > 0$ , $lim_{n \to \infty} P (| H_{j}^{(n)} - π_{j} | > ε) = 0,$ independent of the starting state $X_{0} = i$ .

A stronger result:

Theorem (Ergodic Theorem)

Let ${X_{n} | n \in N_{0}}$ be an irreducible, positive recurrent MC on state space $S$ and stationary distribution $π$ . Suppose $g : S \to R$ be a function s.t. $\sum_{i \in S} g (i) π_{i} < \infty$ . Then for any initial distribution for $X_{0}$ , $\frac{1}{n} \sum_{k = 1}^{n} g (X_{k}) \overset{a . s .}{\to} \sum_{i \in S} g (i) π_{i}, n \to \infty .$

3 First Passage Time

First Passage time

For $i \in S$ , $T_{i} = min {n \in N | X_{n} = i}$ .

Fundamental Matrix of Irreducible MC

$Z = (I - P + 1 π)^{- 1}$ .

$Z$ is well defined.

If the MC is aperiodic, then $Z = I + \sum_{n = 1}^{\infty} (P^{n} - 1 π)$ .

Mean First Pasage Time

For an irreducible finite Markov Chain with the fundamental matrix $Z_{0} = (z_{i j})$ and the unique stationary distribution $π$ , $E [T_{j} | X_{0} = i] = \frac{Z_{j j} - Z_{i j}}{π_{j}} .$

Suppose a finite MC is not irreducible (i.e., has more than one SCC)
$P$ restricted to each terminal SCC is a valid transition matrix. Then there exists a stationary distribution for each terminal SCC.

4 Reversible MC

Pasted image 20241218225444.png|400

Theorem

Let ${X_{n} | 0 \leq n \leq N}$ be an irreducible positive recurrent MC with transition matrix $P = (p_{i j})$ and unique stationary distribution $π$ . Further, suppose $X_{n} \sim π, \forall 0 \leq N$ . Then the reversed process ${Y_{n} = X_{N - n}, 0 \leq n \leq N}$ is a MC with transition matrix $Q = (q_{i j})$ , where $q_{i j} = \frac{π_{j} p_{j i}}{π_{i}}$ .

Proof

$\begin{aligned} P (Y_{n + 1} = j | Y_{1} = i_{1}, \dots, Y_{n} = i_{n}) \\ = & \frac{P (Y_{0} = i_{0}, \dots, Y_{n} = i_{n}, Y_{n + 1} = j)}{P (Y_{0} = i_{0}, \dots, Y_{n} = i_{n})} \\ = & \frac{P (X_{N} = i_{0}, \dots, X_{N - n} = i_{n}, X_{N - n - 1} = j)}{P (X_{N} = i_{0}, \dots, X_{N - n} = i_{n})} \\ = & \frac{π_{j} P_{j, i_{n}} P_{i_{n}, i_{n - 1}} \dots P_{i_{1}, i_{0}}}{π_{i_{n}} P_{i_{n}, i_{n - 1}} \dots P_{i_{1}, i_{0}}} \\ = & P (X_{N - n - 1} = j | X_{N - n} = i_{n}) \\ = & P (Y_{n + 1} = j | Y_{n} = i_{n}) \end{aligned}$

Reversibility

The chain ${X_{n}}$ is said to be reversible if $q_{i j} = p_{i j}$ , $\forall i, j$ . That is, detailed balance $π_{j} p_{j i} = π_{i} p_{i j}, \forall i, j .$

Theorem

Let ${X_{n}}$ be an irreducible Markov Chain with transition matrix $P = (p_{i j})$ and suppose $\exists$ a distribution $ν = (ν_{i})$ s.t. $ν_{i} p_{i j} = ν_{j} p_{j i}$ , $\forall i, j$ . Then $ν$ is a stationary distribution of the chain and ${X_{n}}$ is reversible in equilibrium.

Proof

Since $\sum_{i} ν_{i} p_{i j} = \sum_{i} ν_{j} p_{j i} = ν_{j} \sum_{i} p_{j i} = ν_{j},$ then $ν$ is a stationary distribution. Reversibility of ${X_{n}}$ follows from definition.